package question.solution1558;
import	java.util.ArrayList;
import java.util.ArrayList;
import	java.util.HashMap;

import question.SolutionTemplate;

import java.util.Map;

public class Solution1558 implements SolutionTemplate {

    /***
     * 状态转移方程
     * if a%2 ==0 && b%2 ==0:
     *   dp(a,b) = min(dp(a-1,b)+1, dp(a,b-1)+1, dp(a/2,b/2)+1)
     * else :
     *   dp(a,b) = min(dp(a-1,b)+1, dp(a,b-1)+1)
     *
     * 有内存溢出问题 [1000000000]
     */
    public int minOperations(int[] nums) {
        int possibleCount = 1;
        for(int num : nums){
            possibleCount *= (num+1);
        }
        Map<String, Integer> record = new HashMap<String, Integer> (possibleCount);
        return dp(nums, record);
    }

    private int dp(int[] nums,Map<String, Integer> records){
        String numString = getString(nums);
        System.out.println(numString);
        if(null != records.get(numString)){
            return records.get(numString);
        }
        boolean allEven = true;
        int sumOfNums = 0;
        for(int num:nums){
            sumOfNums += num;
            if(num % 2 != 0){
                allEven = false;
            }
        }
        int result;
        if(sumOfNums == 0){
            result =0;
            records.put(numString, result);
            return 0;
        }
        if(sumOfNums == 1){
            result =1;
            records.put(numString, result);
            return 1;
        }
        if(allEven){
            result =Math.min(halfDp(nums, records), partMin(nums, records));
            records.put(numString, result);
            return result;
        }else{
            result = partMin(nums, records);
            records.put(numString, result);
            return result;
        }
    }

    private int partMin(int[] nums, Map<String, Integer> records){
        int[] partDp = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            nums[i] = nums[i]-1;
            if(nums[i]<0){
                partDp[i] = Integer.MAX_VALUE;
            }else{
                partDp[i] = dp(nums, records)+1;
            }
            nums[i] = nums[i]+1;
        }
        return min(partDp);
    }

    private int halfDp(int[] nums,Map<String, Integer> records){
        for(int i=0;i<nums.length;i++){
            nums[i] = nums[i] / 2;
        }
        int halfDp = dp(nums,records);
        for(int i=0;i<nums.length;i++){
            nums[i] = nums[i] * 2;
        }
        return halfDp + 1;
    }

    private int min(int[] nums){
        int min = Integer.MAX_VALUE;
        for(int num: nums){
            min = Math.min(min, num);
        }
        return min;
    }

    private String getString(int[] nums){
        StringBuffer stringBuffer = new StringBuffer();
        for(int num: nums){
            stringBuffer.append(num + ",");
        }
        return stringBuffer.toString();
    }

    /***
     *  别人的牛逼方法
     */
    public int minOperations2(int[] nums) {
        int multiply = 0, plusOne = 0;
        int max = 0;
        for (int num: nums) {
            max = Math.max(max, num);
            while (num > 0) {
                num &= (num-1);
                plusOne++;
            }
        }
        while (max > 0) {
            max >>= 1;
            multiply++;
        }
        return multiply+plusOne-1;
    }

    @Override
    public void test() {
        int[] nums = {1000000000};
        int result = minOperations(nums);
        System.out.println(result);
    }
}
